package queue

// Queue 先定义队列的需要实现的规范 最主要的就是出队 入队
// 出入队的情况下 还有 是否满 是否空
type Queue interface {
	// Enq Go 暂时还不支持泛型 只能用 interface 类型接收 入队
	Enq(e byte)

	// Deq 出队
	Deq() byte

	// 定义： front 永远指向队列的头节点  tear 永远指向没有元素的队尾  如果front == tear 代表 头为空 即整个队列都为空
	// 但是会 发现一个问题, p1图可以看到, front 指向 a[2] 但是 rear 已经假溢出 指向的越界位置

	// 为了在连续空间的 固定有限空间完成 队列的使用, 当rear越界 可以重新排到空闲的 a[0] 位置, 当队列满的时候发现 front == rear
	// 这就出现了一个问题  就是仅仅 front == rear 无法判断当前队列 是满 还是空
	// 导致 满 == 条件是因为入队 引入一个临时变量 enq_op = false 出队 = true 入队, 这个标识 永远都记录 上一次动作的状态
	// if front == rear && enq_op  == true 代表队列满,  == false 代表队列空
	// 初始状态 front == rear 是空, enq_op = false.

	// IsEmpty 是否空
	IsEmpty() bool

	// IsFull 是否满
	IsFull() bool
}

// 环形队列在 linux 操作系统的 管道中被适用, 使用一个固定长度的 4kb
// 数据存储方面通常适用字节为单位;  4 kb = 4 * 1024 bytes = 4096 bytes
// 数据传输以比特为单位(01电气信号);
// 环形队列结构被广泛使用;

// RingQueue 环形队列 可固定长度 可默认长度
// go的构造方法：
type RingQueue struct {
	// 定义真正的存储结构 使用一个数组来存储  这个主要是在 函数传递的时候 函数压栈 会创建数组的副本 如果仅仅是可读没有任何问题
	// 数组和切片的区别：		切片：引用数据类型  数组：值类型
	// 我们直接使用数组 使用字节存储
	Arr [4]byte
	// 定义头和尾两个索引 创建的时候两个相同

	// 读写的位置, 操作系统就是可读 可写;
	// 代表可读的索引
	Front int
	// 代表可写的索引
	Rear int

	// 关键就是判断可读可写 如果 rear 追上了 front 就代表是 空, 如果是 front 追上了 rear 就代表了满;
	// 可以引入一个 flag;

	// 定义上一动作是出队 还是 入队
	// 优化 约定 front 在 rear 下一个位置 为 满  这种方式其实很容易 理解
	Op bool
}

// NewRingQueue go 的创建构造方法
func NewRingQueue() *RingQueue {
	// new关键字：用来分配内存 allocate memory and return a pointer to this memory, zero value of that type.
	// new 就是相当于java中隐藏的 空参构造方法 一样
	// c := new(RingQueue)
	// 否则直接使用 struct 的名称创建取地址
	return new(RingQueue)
}

// Enq 下面我们需要对这个结构体 实现我们规范的队列方法
func (q *RingQueue) Enq(e byte) {
	// 需要划分界限  如果 head == tail 就代表是队列已经空了;
	// 每次入队前 应该判断 队列是否已经满了
	if q.IsFull() {
		panic("Queue is Full, cannot enqueue anything any more")
	}

	// 让tear的值复制
	q.Arr[q.Rear] = e

	// 让Rear往后移动 不能使用三元表达式 这两个索引 [0, len) 之间
	if q.Rear+1 < len(q.Arr) {
		q.Rear++
	} else {
		q.Rear = (q.Rear + 1) % len(q.Arr)
	}

	if q.Rear == q.Front {
		q.Op = true
	}
}

func (q *RingQueue) Deq() byte {
	if q.IsEmpty() {
		panic("Queue is Empty, cannot dequeue anything any more")
	}

	// 先取出 数据
	b := q.Arr[q.Front]
	// 让front往后移动 不能使用三元表达式
	if q.Front+1 < len(q.Arr) {
		q.Front++
	} else {
		q.Front = (q.Front + 1) % len(q.Arr)
	}

	if q.Rear == q.Front {
		q.Op = false
	}

	return b
}

func (q *RingQueue) IsEmpty() bool {
	return q.Rear == q.Front && !q.Op
}

func (q *RingQueue) IsFull() bool {
	return q.Rear == q.Front && q.Op
}
